from random import randint
import time

n = int(input())

data = []
for i in range(n):
    data.append(randint(0,n*n))

# print data
print 'insert sort begin:'
print ' running...'
t1 = int(time.time()*1000)
for i in range(1,n):
    x=data[i]
    j=i
    while j>0 and data[j-1]>x :
        data[j]=data[j-1]
        j-=1
    data[j]=x
t2 = int(time.time()*1000)

# print data
p = True
for i in range(n-1):
    if data[i]>data[i+1] :
        p = False
        break

print 'inset sort end.'
print 'run time: %dms'%(t2-t1)
